﻿#include <QCoreApplication>
#include <iostream>
#include <QTextStream>
using namespace std;

QString getLongestCommonPrefix(QList<QString> strs);

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QTextStream in(stdin);
    QTextStream out(stdout);
    QList<QString> strs;
    QString str="";

    while(1)
    {
        cout<<"*****************************************寻找字符串的最长公共前缀********************************************"<<endl;

        cout<<endl;
        cout<<"请输入两个或两个以上的字符串（每个字符串之间以任意长的空格分隔，按回车键结束输入）："<<endl;
        str=in.readLine();     //读取一行，以回车键为结束
        strs=str.split(" ",QString::SkipEmptyParts);     //将字符串按空格进行分隔，空格可以为任意宽度
        cout<<endl;

        if(strs.size()>1)     //必须两个或两个以上的字符串才能进行比较，否则需要重新输入
        {
            QString commonPrefix = getLongestCommonPrefix(strs);     //调用getLongestCommonPrefix函数

            if(commonPrefix=="")
            {
                cout<<"这些字符串没有公共前缀"<<endl;
            }else
            {
                cout<<"这些字符串的公共前缀为：";
                out<<commonPrefix<<endl;
            }

        }else
        {
            cout<<"输入有误，请重新输入！"<<endl;
        }

        cout<<endl;
        system("pause");
        system("cls");
    }

    return a.exec();
}

QString getLongestCommonPrefix(QList<QString> strs)
{
    QString str="";
    int minLength=strs[0].size();

    for(int i=1;i<strs.size();++i)
    {
        if(strs[i].size()<minLength)
        {
            minLength=strs[i].size();     //找出最短字符串的长度
        }
    }

    for(int i=0;i<minLength;++i)
    {
        int findCommonPrefix=1;     //设置公共前缀是否已经寻找结束的标志，1代表继续寻找，0代表已经寻找结束

        for (int j = 1; j < strs.size(); ++j)
        {
            if(strs[j][i]!=strs[0][i])     //将所有的字符串对应位置的字符一一进行比较，一旦出现不匹配，寻找结束
            {
                findCommonPrefix=0;
                break;
            }
        }

        if(findCommonPrefix==0)break;

        str.append(strs[0][i]);     //将公共的字符逐个添加在输出字符串的末尾
    }

    if(str.isEmpty())     //如果输出字符串的大小为0，返回空字符串
    {
        return "";
    }

    return str;
}
